package leetcode_bin_tree_test;

import bin_tree.MyBinTree.BinTreeNode;
import bin_tree_order.Main;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * 根据二叉树创建字符串
 */
public class CreatesString {
    public static String tree2str(BinTreeNode root) {
        // 递归
        // 括号是为了分清左右子树，不必要的空括号是右树
        // 前序遍历
//        if (root == null) {
//            return "";
//        }
//        StringBuilder str = new StringBuilder();
//        str.append(root.val);
//        if (root.left == null && root.right == null) {
//            return str.toString();
//        }
//        str.append("(");
//        if (root.left != null) {
//            str.append(tree2str(root.left));
//        }
//        str.append(")");
//        if (root.right != null) {
//            str.append("(");
//            str.append(tree2str(root.right));
//            str.append(")");
//        }
//        return str.toString();

        // 迭代
        if (root == null) {
            return "";
        }
        StringBuilder str = new StringBuilder();
        Deque<BinTreeNode> stack = new ArrayDeque<>();
        Set<BinTreeNode> set = new HashSet<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            BinTreeNode node = stack.peek();
            if (set.contains(node)) {
                stack.pop();
                str.append(")");
            } else {
                str.append("(" + node.val);
                set.add(node);
                if (node.left == null && node.right != null) {
                    str.append("()");
                }
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
        }
        return str.substring(1, str.length() - 1);
    }

    public static void main(String[] args) {
        BinTreeNode root = new BinTreeNode('1');
        BinTreeNode l1 = new BinTreeNode('2');
        BinTreeNode l2 = new BinTreeNode('3');
        BinTreeNode r1 = new BinTreeNode('4');
        root.left = l1;
        l1.right = l2;
        root.right = r1;
        System.out.println(tree2str(root));
    }
}

